home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / euphoria / allsorts.ex next >
Text File  |  1994-02-15  |  8KB  |  373 lines

  1.         ----------------------------------------
  2.         -- Sorting Algorithms in Euphoria     --
  3.         -- These routines will sort sequences --
  4.         -- of general Euphoria objects          --
  5.         ----------------------------------------
  6. without type_check
  7.  
  8. constant MAX = 4800
  9. constant TRUE = 1, FALSE = 0
  10. constant CHECK_RESULTS = FALSE
  11.  
  12. integer hybrid_limit
  13.  
  14. type natural(integer x)
  15.     return x >= 0
  16. end type
  17.  
  18. type file_number(integer x)
  19.     return x >= -1
  20. end type
  21.  
  22. function simple_sort(sequence x)
  23. -- put x into ascending order
  24. -- using a very simple sort
  25. object temp
  26.  
  27.     for i = 1 to length(x) - 1 do
  28.     for j = i + 1 to length(x) do
  29.         if compare(x[j],x[i]) < 0 then
  30.         temp = x[j]
  31.         x[j] = x[i]
  32.         x[i] = temp
  33.         end if
  34.     end for
  35.     end for
  36.     return x
  37. end function
  38.  
  39.  
  40. function bubble_sort(sequence x)
  41. -- put x into ascending order
  42. -- using bubble sort
  43. object temp
  44. natural flip, limit
  45.  
  46.     flip = length(x)
  47.     while flip > 0 do
  48.     limit = flip
  49.     flip = 0
  50.     for i = 1 to limit - 1 do
  51.         if compare(x[i+1], x[i]) < 0 then
  52.         temp = x[i+1]
  53.         x[i+1] = x[i]
  54.         x[i] = temp
  55.         flip = i
  56.         end if
  57.     end for
  58.     end while
  59.     return x
  60. end function
  61.  
  62. function insertion_sort(sequence x)
  63. -- put x into ascending order
  64. -- using insertion sort
  65. object temp
  66. natural final
  67.  
  68.     for i = 2 to length(x) do
  69.     temp = x[i]
  70.     final = 1
  71.     for j = i-1 to 1 by -1 do
  72.         if compare(temp, x[j]) < 0 then
  73.         x[j+1] = x[j]
  74.         else
  75.         final = j + 1
  76.         exit
  77.         end if
  78.     end for
  79.     x[final] = temp
  80.     end for
  81.     return x
  82. end function
  83.  
  84. function shell_sort(sequence x)
  85. -- Shell sort based on insertion sort
  86.  
  87.     integer gap, j, first, last
  88.     object tempi, tempj
  89.  
  90.     last = length(x)
  91.     gap = floor(last / 3) + 1
  92.     while TRUE do
  93.     first = gap + 1
  94.     for i = first to last do
  95.         tempi = x[i]
  96.         j = i - gap
  97.         while TRUE do
  98.         tempj = x[j]
  99.         if compare(tempi, tempj) >= 0 then
  100.             j = j + gap
  101.             exit
  102.         end if
  103.         x[j+gap] = tempj
  104.         if j <= gap then
  105.             exit
  106.         end if
  107.         j = j - gap
  108.         end while
  109.         x[j] = tempi
  110.     end for
  111.     if gap = 1 then
  112.         return x
  113.     else
  114.         gap = floor(gap / 3) + 1
  115.     end if
  116.     end while
  117. end function
  118.  
  119.  
  120. global function quick_sort(sequence x)
  121. -- put x into ascending order
  122. -- using recursive quick sort
  123.     natural n, last, midval, temp
  124.  
  125.     n = length(x)
  126.     if n < 2 then
  127.     return x -- already sorted (trivial case)
  128.     end if
  129.  
  130.     midval = x[(n + 1) / 2]
  131.     x[(n + 1) / 2] = x[1]
  132.  
  133.     last = 1
  134.     for i = 2 to n do
  135.     if compare(x[i], midval) < 0 then
  136.         last = last + 1
  137.         temp = x[last]  x[last] = x[i]  x[i] = temp
  138.     end if
  139.     end for
  140.  
  141.     return quick_sort(x[2..last]) & {midval} & quick_sort(x[last+1..n])
  142. end function
  143.  
  144.  
  145. global function hybrid_sort(sequence x)
  146. -- put x into ascending order
  147. -- using recursive quick sort
  148. -- but call insertion sort for short sequences
  149.     natural n, last, midpt
  150.     object midval, temp
  151.  
  152.     n = length(x)
  153.     if n < hybrid_limit then
  154.     return insertion_sort(x)
  155.     end if
  156.  
  157.     midpt = floor((n + 1) / 2)
  158.     midval = x[midpt]
  159.     x[midpt] = x[1]
  160.  
  161.     last = 1
  162.     for i = 2 to n do
  163.     if compare(x[i], midval) < 0 then
  164.         last = last + 1
  165.         temp = x[last]  x[last] = x[i]  x[i] = temp
  166.     end if
  167.     end for
  168.  
  169.     return hybrid_sort(x[2..last]) & {midval} & hybrid_sort(x[last+1..n])
  170. end function
  171.  
  172. sequence x
  173.  
  174. procedure g_insertion_sort()
  175. -- put global variable x into ascending order
  176. -- using insertion sort of general objects
  177. object temp
  178. natural final
  179.  
  180.     for i = 2 to length(x) do
  181.     temp = x[i]
  182.     final = 1
  183.     for j = i-1 to 1 by -1 do
  184.         if compare(temp, x[j]) < 0 then
  185.         x[j+1] = x[j]
  186.         else
  187.         final = j + 1
  188.         exit
  189.         end if
  190.     end for
  191.     x[final] = temp
  192.     end for
  193. end procedure
  194.  
  195. procedure best_sort(natural m, natural n)
  196. -- put x into ascending order
  197. -- using recursive quick sort
  198.     natural last, midpt
  199.     object midval, temp
  200.  
  201.     if n - m < 20 then -- 10 or 20
  202.     return
  203.     end if
  204.  
  205.     midpt = floor((m + n) / 2)
  206.     midval = x[midpt]
  207.     x[midpt] = x[m]
  208.  
  209.     last = m
  210.     for i = m+1 to n do
  211.     if compare(x[i], midval) < 0 then
  212.         last = last + 1
  213.         temp = x[last]  x[last] = x[i]  x[i] = temp
  214.     end if
  215.     end for
  216.     x[m] = x[last]
  217.     x[last] = midval
  218.     best_sort(m, last-1)
  219.     best_sort(last+1, n)
  220. end procedure
  221.  
  222. global function great_sort(sequence a)
  223. -- Avoids dynamic storage allocation - just passes indexes into
  224. -- a global sequence.
  225. -- Not much better than hybrid_sort which makes full use of dynamic
  226. -- storage allocation.
  227. -- Note that we only partition down to a certain degree, then do an
  228. -- insertion sort which will run fast because things are roughly in order.
  229. -- See Knuth for the details
  230.     x = a
  231.     best_sort(1, length(x))
  232.     g_insertion_sort()
  233.     return x
  234. end function
  235.  
  236. global function merge_sort(sequence x)
  237. -- put x into ascending order
  238. -- using recursive merge sort
  239.     natural n
  240.     sequence x1, x2, newx
  241.  
  242.     n = length(x)
  243.     if n < 2 then
  244.     return x
  245.     end if
  246.  
  247.     x1 = merge_sort(x[1..n/2])
  248.     x2 = merge_sort(x[n/2+1..n])
  249.     newx = {}
  250.     while length(x1) > 0 and length(x2) > 0 do
  251.     if compare(x1[1], x2[1]) < 0 then
  252.         newx = append(newx, x1[1])
  253.         x1 = x1[2..length(x1)]
  254.     else
  255.         newx = append(newx, x2[1])
  256.         x2 = x2[2..length(x2)]
  257.     end if
  258.     end while
  259.     newx = newx & x1 & x2 -- one will be empty
  260.     return newx
  261. end function
  262.  
  263. procedure check_results(sequence sdata, sequence data)
  264. -- compare results with another sort to make sure they are correct
  265.     if CHECK_RESULTS then
  266.         if compare(sdata, shell_sort(data)) != 0 then
  267.         puts(2, "\nabort!\n")
  268.         print(2, 1/0)
  269.         end if
  270.     end if
  271. end procedure
  272.  
  273. procedure all_sorts()
  274. -- test all sorting routines over a range of numbers of items
  275.  
  276.     file_number printer
  277.     natural nitems, iterations
  278.     atom t0, t
  279.     sequence data, sdata
  280.  
  281.     printer = 1   -- open("PRN", "w")
  282.     nitems = 5
  283.     while nitems <= MAX do
  284.     -- get several sets of data of length nitems
  285.     iterations = floor(MAX/nitems)
  286.     if iterations > 500 then
  287.         iterations = 500
  288.     end if
  289.     printf(printer, "\ntime (sec.) to sort %d items (averaged over %d trials)\n",
  290.             {nitems, iterations})
  291.  
  292.     data = rand(repeat(repeat(nitems, nitems), iterations))
  293.     t0 = time()
  294.     for i = 1 to iterations do
  295.         sdata = bubble_sort(data[i])
  296.         check_results(sdata, data[i])
  297.     end for
  298.     t = time() - t0
  299.     printf(printer, "bubble sort   %9.4f\n", t/iterations)
  300.  
  301.     t0 = time()
  302.     for i = 1 to iterations do
  303.         sdata =  simple_sort(data[i])
  304.         check_results(sdata, data[i])
  305.     end for
  306.     t = time() - t0
  307.     printf(printer, "simple sort   %9.4f\n", t/iterations)
  308.  
  309.     t0 = time()
  310.     for i = 1 to iterations do
  311.         sdata = insertion_sort(data[i])
  312.         check_results(sdata, data[i])
  313.     end for
  314.     t = time() - t0
  315.     printf(printer, "insertion sort%9.4f\n", t/iterations)
  316.  
  317.     t0 = time()
  318.     for i = 1 to iterations do
  319.         sdata = shell_sort(data[i])
  320.         check_results(sdata, data[i])
  321.     end for
  322.     t = time() - t0
  323.     printf(printer, "shell sort    %9.4f\n", t/iterations)
  324.  
  325.     t0 = time()
  326.     for i = 1 to iterations do
  327.         sdata = merge_sort(data[i])
  328.         check_results(sdata, data[i])
  329.     end for
  330.     t = time() - t0
  331.     printf(printer, "merge sort    %9.4f\n", t/iterations)
  332.  
  333.     t0 = time()
  334.     for i = 1 to iterations do
  335.         sdata = quick_sort(data[i])
  336.         check_results(sdata, data[i])
  337.     end for
  338.     t = time() - t0
  339.     printf(printer, "quick sort    %9.4f\n", t/iterations)
  340.  
  341.     for hl = 20 to 20 by 2 do
  342.         hybrid_limit = hl
  343.         t0 = time()
  344.         for i = 1 to iterations do
  345.         sdata = hybrid_sort(data[i])
  346.         check_results(sdata, data[i])
  347.         end for
  348.         t = time() - t0
  349.         printf(printer, "hybrid sort-%d%9.4f\n", {hybrid_limit,t/iterations})
  350.     end for
  351.  
  352.     for hl = 20 to 20 by 2 do
  353.         hybrid_limit = hl
  354.         t0 = time()
  355.         for i = 1 to iterations do
  356.         sdata = great_sort(data[i])
  357.         check_results(sdata, data[i])
  358.         end for
  359.         t = time() - t0
  360.         printf(printer, "great sort-%d %9.4f\n", {hybrid_limit,t/iterations})
  361.     end for
  362.  
  363.     puts(1, "\nPress Enter to continue, q to quit: ")
  364.     if find('q', gets(0)) then
  365.         abort(1)
  366.     end if
  367.     nitems = nitems * 2
  368.     end while
  369. end procedure
  370.  
  371. all_sorts()
  372.  
  373.